#include <bits/stdc++.h>

using namespace std;

const int maxn=305;
const int inf=~0U>>3;

int f[10][maxn][maxn];
int _p[2][maxn][maxn];
int (*p)[maxn],(*q)[maxn];
template <typename T> inline void read(T &r){
    char c;bool _f=0;
    for(c=getchar();c>'9'||c<'0';c=getchar()) if(c=='-') _f=1;
    for(r=0;c<='9'&&c>='0';c=getchar()) r=r*10+c-'0';
    if(_f) r=-r;
}

template <typename T> inline void clear(T arr,const int &n){
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            arr[i][j]=inf;
}

int main(){
    int n,m;

    read(n);read(m);
    clear(f[0],n);
    for(int i=0;i<m;i++){
        int x,y;
        read(x);read(y);read(f[0][x][y]);
    }
    int lg=0;bool flag=1;
    for(int i=1;i<=n;i++) f[0][i][i]=0;
    for(;flag&&(1<<lg)<=n;lg++){
        clear(f[lg+1],n);
        for(int k=1;k<=n;k++)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    if((f[lg+1][i][j]=min(f[lg+1][i][j],f[lg][i][k]+f[lg][k][j]))<0&&i==j) flag=0;
    }
    if(flag) puts("0");
    else{
        int ans;
        ans=0;
        p=_p[0];q=_p[1];
        clear(p,n);
        for(int i=1;i<=n;i++) p[i][i]=0;
        for(;lg>=0;lg--){
            try{
                clear(q,n);
                for(int k=1;k<=n;k++)
                    for(int i=1;i<=n;i++)
                        for(int j=1;j<=n;j++)
                            if((q[i][j]=min(q[i][j],p[i][k]+f[lg][k][j]))<0&&i==j) throw(true);
                ans|=1<<lg;swap(p,q);
            }catch(bool){}
        }
        printf("%d\n",ans+1);
    }

    return 0;
}
